{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b80ec552",
   "metadata": {},
   "source": [
    "## 归并排序\n",
    "def merge_sort(array, verbose = True)\n",
    "    递归结束条件\n",
    "    二分法，将array划分为left,right\n",
    "    递归调用\n",
    "\n",
    "    初始化：子数组 | 头指针\n",
    "    归并排序：以对应元素进行比较\n",
    "        循环体条件\n",
    "            归并逻辑\n",
    "        对于超出数组索引范围的情况进行处理"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "6453475e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "braek array [38, 27, 43, 3, 9, 89, 64, 10] into subarray: left >[38, 27, 43, 3]< and right >[9, 89, 64, 10] <.\n",
      "braek array [38, 27, 43, 3] into subarray: left >[38, 27]< and right >[43, 3] <.\n",
      "braek array [38, 27] into subarray: left >[38]< and right >[27] <.\n",
      "merge array >[38]< and >[27]< into >[27, 38]< .\n",
      "braek array [43, 3] into subarray: left >[43]< and right >[3] <.\n",
      "merge array >[43]< and >[3]< into >[3, 43]< .\n",
      "merge array >[27, 38]< and >[3, 43]< into >[3, 27, 38, 43]< .\n",
      "braek array [9, 89, 64, 10] into subarray: left >[9, 89]< and right >[64, 10] <.\n",
      "braek array [9, 89] into subarray: left >[9]< and right >[89] <.\n",
      "merge array >[9]< and >[89]< into >[9, 89]< .\n",
      "braek array [64, 10] into subarray: left >[64]< and right >[10] <.\n",
      "merge array >[64]< and >[10]< into >[10, 64]< .\n",
      "merge array >[9, 89]< and >[10, 64]< into >[9, 10, 64, 89]< .\n",
      "merge array >[3, 27, 38, 43]< and >[9, 10, 64, 89]< into >[3, 9, 10, 27, 38, 43, 64, 89]< .\n",
      "[3, 9, 10, 27, 38, 43, 64, 89]\n"
     ]
    }
   ],
   "source": [
    "def merge_sort(array, verbose=True):\n",
    "    if len(array) <= 1:\n",
    "        return array\n",
    "    mid = int(len(array) / 2)\n",
    "    left = array[0:mid]\n",
    "    right = array[mid:]\n",
    "\n",
    "    if verbose:\n",
    "        print(\"braek array {0} into subarray: left >{1}< and right >{2} <.\".format(array, left, right))\n",
    "\n",
    "    left_sorted = merge_sort(left)\n",
    "    right_sorted = merge_sort(right)\n",
    "\n",
    "    merge_array = []\n",
    "    i = 0\n",
    "    j = 0\n",
    "    while i < len(left_sorted) and j < len(right_sorted):\n",
    "        if left_sorted[i] <= right_sorted[j]:\n",
    "            merge_array.append(left_sorted[i])\n",
    "            i += 1\n",
    "        else: \n",
    "            merge_array.append(right_sorted[j])\n",
    "            j += 1\n",
    "        if i >= len(left_sorted):\n",
    "            merge_array.extend(right_sorted[j:])\n",
    "            break\n",
    "        elif j >= len(right_sorted):\n",
    "            merge_array.extend(left_sorted[i:])\n",
    "            break\n",
    "    if verbose:\n",
    "        print(\"merge array >{0}< and >{1}< into >{2}< .\".format(left_sorted, right_sorted, merge_array))\n",
    "\n",
    "    return merge_array\n",
    "\n",
    "array = [38, 27, 43, 3, 9, 89, 64, 10]\n",
    "arr_sorted = merge_sort(array)\n",
    "print(arr_sorted)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
